package com.fyl.leetcode.backtracking;

/**
 * @author:fyl
 * @date 2021/5/22 15:47
 * @Modified By:
 * @Modified Date:
 * @Description:
 * For example,
 * Given board =
 * [
 *   ['A','B','C','E'],
 *   ['S','F','C','S'],
 *   ['A','D','E','E']
 * ]
 * word = "ABCCED", -> returns true,
 * word = "SEE", -> returns true,
 * word = "ABCB", -> returns false.
 */
public class WordSearch {
    private final int[][] direction = {{0, 1}, {0, -1}, {1, 0}, {-1, 0}};

    public boolean exist(char[][] board, String word) {
        char[] words = word.toCharArray();
        int count = 0;
        boolean[][] visited = new boolean[board.length][board[0].length];
        for (int i = 0; i < board.length; i++) {
            for (int j = 0; j < board[i].length; j++) {
                if (def(0, i, j, visited, board, word)) {
                    return true;
                }
            }
        }
        return false;
    }

    private boolean def(int cur, int i, int j, boolean[][] visited, char[][] board, String word) {
        if (cur == word.length()) {
            return true;
        }
        if (i < 0 || j < 0 || i >= board.length || j >= board[i].length ||
                board[i][j] != word.charAt(cur) || visited[i][j]) {  //访问过的以及该位置的字母不等于word当前字符时，返回false
            return false;
        }
        visited[i][j] = true;
        for (int[] dir : direction) {
            if (def(cur + 1, i + dir[0], j + dir[1], visited, board, word)) {
                return true;
            }
        }
        //将访问标记复原，便于下次访问。
        visited[i][j] = false;
        return false;
    }
}
